#pragma once;

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <string>
#include <stack>
#include <exception>
#include <boost/shared_ptr.hpp>
#include <boost/shared_array.hpp>

using namespace std;

namespace yet{

#define CR	'\r'
#define LF	'\n'

#ifndef Min

#define Max(a,b)    (((a) > (b)) ? (a) : (b))
#define Min(a,b)    (((a) < (b)) ? (a) : (b))

#define Max3(a, b, c)	Max(Max(a, b), c)
#define Min3(a, b, c)   Min(Min(a, b), c)
#endif

inline int clip(int minVal, int maxVal, int val) {
	if (val < minVal) {
		return minVal;
	}
	if (val > maxVal) {
		return maxVal;
	}
	return val;
}

inline bool InRange00(int start, int end, int value) {
	return value > start && value < end;
}
inline bool InRange01(int start, int end, int value) {
	return value > start && value <= end;
}
inline bool InRange10(int start, int end, int value) {
	return value >= start && value < end;
}
inline bool InRange11(int start, int end, int value) {
	return value >= start && value <= end;
}

inline bool InRangeX00(int start, int end, int value) {
	return value > min(start, end) && value < max(start, end);
}
inline bool InRangeX01(int start, int end, int value) {
	return value > min(start, end) && value <= max(start, end);
}
inline bool InRangeX10(int start, int end, int value) {
	return value >= min(start, end) && value < max(start, end);
}
inline bool InRangeX11(int start, int end, int value) {
	return value >= min(start, end) && value <= max(start, end);
}

inline bool isCR(char ch) {
	return ch == CR;
}
inline bool isLF(char ch) {
	return ch == LF;
}
inline bool isCROrLF(char ch) {
	return ch == CR || ch == LF;
}

//count is array length, not bytes
template<typename T>
void inline MemMove(T* dest, const T* src, size_t count) {
	if (count && dest && src && dest != src) {
		memmove(dest, src, sizeof(T) * count);
	}
}
////sizeof(void) ?, so , if given void*
//template<>
//void MemMove(void* dest, const void* src, size_t bytes) {
//	if (bytes && dest && src && dest != src) {
//		memmove(dest, src, bytes);
//	}
//}
template<typename T>
void ArrayMove(T* dest, const T* src, size_t count) {
	if (count && dest && src && dest != src) {
		if (dest < src) {
			while (count--) {
				*dest++ = *src++;
			}
		} else { //dest > src
			dest += count;
			src += count;
			while (count--) {
				*--dest = *--src;
			}
		}
	}
}
template<typename T>
void ArrayMove(T* dest, size_t destFrom, const T* src, size_t srcFrom,
		size_t count) {
	if (count && dest && src && (dest + destFrom) != (src + srcFrom)) {
		dest += destFrom;
		src += srcFrom;
		if (dest < src) {
			while (count--) {
				*dest++ = *src++;
			}
		} else { //dest > src
			dest += count;
			src += count;
			while (count--) {
				*--dest = *--src;
			}
		}
	}
}
template<typename T>
void inline RangeSet(T* array, size_t count, const T& value) {
	if (array && count) {
		for (size_t i = 0; i < count; ++i) {
			array[i] = value;
		}
	}
}
template<typename T>
void inline RangeSet(T* array, size_t from, size_t count, const T& value) {
	if (array && count) {
		for (size_t i = 0; i < count; ++i) {
			array[i + from] = value;
		}
	}
}

template<typename T>
void inline ArraySet(T* array, size_t length, T value) {
	for (int i = 0; i < length; ++i) {
		array[i] = value;
	}
}
template<typename T>
void inline Zero(T* array, size_t length) {
	memset(array, 0, sizeof(T) * length);
}

class InvalidIndexException: public exception {

};

class NegtiveIndexException: public InvalidIndexException {

};
class IndexOutOfBoundException: public InvalidIndexException {

};
class NotFoundException: public std::exception {

};

class InvalidArgumentException: public exception {

};

template<typename T>
class AutoBuffer {
private:
	AutoBuffer(const AutoBuffer<T>& other);
	AutoBuffer<T> operator=(const AutoBuffer<T>& other);
public:
	virtual ~AutoBuffer() {
		release();
	}
	inline AutoBuffer() :
			buffer(0), length(0) {

	}
	inline AutoBuffer(int len):
			buffer(0) {
		init(len);
	}
public:
	inline void init(int len) {
		release();
		assert(len >0);
		buffer = new T[len];
		length = len;
	}
	inline void release() {
		if (buffer) {
			delete[] buffer;
		}
		buffer = 0;
		length = 0;
	}
	inline T& operator[](int index) {
		assert(index < length);
		return buffer[index];
	}
	//can not return a non-ref value, for example:
	//buff[i].falg = 1
	//flag will not assign to the buffer element, insted, a temp element
//	T operator[](int index) const {
//		assert(index < length);
//		return buffer[index];
//	}
	inline operator T*() {
		return buffer;
	}
	void grab(AutoBuffer<T>& other) {
		release();
		buffer = other.buffer;
		length = other.length;
		other.buffer = 0;
		other.length = 0;
	}

	inline void discard() {
		buffer = 0;
		length = 0;
	}
public:
	T* buffer;
	int length;
};

template<typename T>
class Stack: public stack<T> {
public:
	void clear() {
//		c.clear();
		while (!empty()) {
			pop();
		}
	}
};

template<typename T>
struct LastValue {
	typedef T result_type;

	template<typename InputIterator>
	T operator()(InputIterator first, InputIterator last) const {
		if (first == last)
			return T();
		T val = *first++;
		while (first != last) {
			val = *first;
			++first;
		}
		return val;
	}
};

template<typename T>
class Range {
public:
	typedef T ValueType;
public:
	int from;
	int to;

	ValueType value;
public:
	inline Range() :
			from(0), to(0) {
		value = ValueType();

	}
	inline Range(int from_, int to_) :
			from(from_), to(to_) {
		value = ValueType();
		if (from > to) {
			throw InvalidArgumentException();
		}
	}
	inline Range(int from_, int to_, ValueType value_) :
			from(from_), to(to_), value(value_) {
		if (from > to) {
			throw InvalidArgumentException();
		}
	}
public:
	inline int length() const {
		return to - from;
	}
};

typedef Range<int> IntRange;

template<typename T>
bool operator <(const Range<T>& left, const Range<T>& right) {
	return left.from < right.from;
}
template<typename T>
bool operator ==(const Range<T>& left, const Range<T>& right) {
	return left.from == right.from;
}

class WithTag {
private:
	int tag;
public:
	WithTag();
public:
	void setTag(int tag_);
	int getTag();
};

//return value > 0 if found;
//else ~value is the insert pos.
int binarySearch(const int* a, int start, int len, int key);
inline int binarySearch(const int* a, int len, int key){
	return binarySearch(a, 0, len, key);
}

}
